class Solution {
    public int[] memo;
    public int lengthOfLIS(int[] nums) {
        int ans=0;
        int n= nums.length;
        memo=new int[n];
        for (int i = 0; i < n; i++) {
            ans=Math.max(ans,dfs(nums,i));
        }
        return ans;
    }
    public int dfs(int[] nums,int pos){
        if(memo[pos]!=0){
            return memo[pos];
        }
        int ans=1;
        for(int i=pos+1;i<nums.length;i++){
            if(nums[i]>nums[pos]){
                ans=Math.max(ans,dfs(nums,i)+1);
            }
        }
        memo[pos]=ans;
        return ans;
    }
}